package ShortestPath;

import java.util.ArrayList;

import Definitions.GraphClass;
import Definitions.NodeClass;
import Global.GlobalClass;

public class ConnectedComponentsAnalyzerInParallelClass {

	
	
	/*	public class ConnectedComponentsAtALevelClass 
		{
			boolean komsulukMatrisiAtThisLevel[][];
			boolean toplamKomsulukMatrisiUntilThisLevel[][];
			int level;	//1:Initial level(Birinci derece komsular)//1,2,3...
		}*/
		
		
		//ArrayList<ConnectedComponentsAtALevelClass> ConnectedComponentsAtDegreeLevelsList;
		int shortestPathArray[][];
		int komsulukMatrisi[][];				//1.seviye komsular, Adjacency matrix		
		int komsulukMatrisiAtLastLevel[][];		
		int lastValidLevel;
		int toplamBulunanYolSayisi;
		
		
		GraphClass localg;
		int localEdgeType;
		int oneDimensionalLength;	//Number of nodes
		
		
		public ConnectedComponentsAnalyzerInParallelClass(GraphClass g, int edgeType)
		{	
			localg=g;
			localEdgeType=edgeType;
			oneDimensionalLength = localg.getDataSet().size();
			System.out.println("cons oneDimensionalLength:"+oneDimensionalLength);
			
			shortestPathArray = new int[oneDimensionalLength][oneDimensionalLength];
			for(int i=0; i<oneDimensionalLength; i++)
				for(int j=0; j<oneDimensionalLength; j++)
					shortestPathArray[i][j]=-1;			
			
			komsulukMatrisi = new int[oneDimensionalLength][oneDimensionalLength];
			
			komsulukMatrisiAtLastLevel = new int[oneDimensionalLength][oneDimensionalLength];
			
			lastValidLevel = 1;
			
			toplamBulunanYolSayisi = 0;
		}
		
		public void calculateAllConnectedComponents(boolean isSymmetric)
		{
			createAdjacencyMatrix();
			//printLastAdjacencyMatrix();					
			
			calculatePowerOfAdjacencyMatrix(oneDimensionalLength, isSymmetric);

			//printShortestArrayMatrix();
		}
		
		void calculatePowerOfAdjacencyMatrix(int power, boolean isSymmetric)
		{
			long processStartTime = 0;
			boolean letsBreak=false;
			
			for(int k=1; k<power; k++)
			{
				//System.out.println("lastValidLevel:"+lastValidLevel+" "+"power"+power);								
				
				processStartTime = System.currentTimeMillis();
				calculateOneStepPowerOfAdjacencyMatrix();
				if(k%100==0)
					System.out.println("Total consumed time:"+(System.currentTimeMillis()-processStartTime)/1000);
				//System.out.println("calculateOneStepPowerOfAdjacencyMatrix:"+k);				
				lastValidLevel = k+1;
				
				if(checkIfItIsTimeStopIterationsOfCalculations(k, isSymmetric))
				{
					System.out.println("It is time to stop at:"+k);
					letsBreak=true;
				}
				else
				{
					System.out.println("Still continue at:"+k);
					//Utility.WorkerUtilityClass.printSeperator();
				}
				
				//System.out.println("Compare Now:"+k);
				//printShortestArrayMatrix();
				//printLastAdjacencyMatrix();
				
				
				updateShortestPathsArray();
				//printMatrix(shortestPathArray, oneDimensionalLength, oneDimensionalLength, "shortestPathArray:");
				
				
				if(letsBreak)
					break;
			}
			
			System.out.println("lastValidLevel son durumda:"+lastValidLevel);
			makeShortestPathCalculationsOverConnectedComponents();
			//ConnectedComponentsAtDegreeLevelsList.get(power);			
		}
		
		void calculateOneStepPowerOfAdjacencyMatrix()
		{
			int sourceMatrix[][], orgAdjacencyMatrix[][];
			//int resultMatrix[][];	
			
			
			sourceMatrix = komsulukMatrisiAtLastLevel;
			orgAdjacencyMatrix = komsulukMatrisi;
			
			int sourceMatrixLength=sourceMatrix.length;
			int orgAdjacencyMatrixLength=orgAdjacencyMatrix.length;
			
			//resultMatrix = new int[sourceMatrixLength][sourceMatrixLength];
			
			//System.out.println("Now printing the details...");
			
			//printMatrix(sourceMatrix, sourceMatrixLength, sourceMatrixLength, "SourceMatrix:");
			//printMatrix(orgAdjacencyMatrix, sourceMatrixLength, sourceMatrixLength, "orgAdjacencyMatrix:");				
			
			komsulukMatrisiAtLastLevel = multiplyMatrices(sourceMatrix, orgAdjacencyMatrix, sourceMatrixLength, sourceMatrixLength, orgAdjacencyMatrixLength, true);					
			
			//printMatrix(toplamKomsulukMatrisiAtLastLevel, sourceMatrixLength, sourceMatrixLength, "toplamKomsulukMatrisiAtLastLevel:");
			
			//System.out.println("The details are printed...");
		}
			
		int[][] addTwoMatrices(int[][] A, int[][] B, int numberOfRows, int numberOfColumns)
		{
			int[][] resultSumMatrix;
			
			resultSumMatrix = new int[numberOfRows][numberOfColumns];
			
			 for(int i = 0; i < numberOfRows; i++)
			 {
			      for(int j = 0; j < numberOfColumns; j++)
			      {
			    	  resultSumMatrix[i][j]=A[i][j] + B[i][j];		    	  
			      }
			 }
			 
			 return resultSumMatrix; 
		}
		
		int[][] multiplyMatrices(int[][] matrixA, int[][] matrixB, int ARowCount, int SharedRowColumnCount, int BColumnCount, boolean isSymmetric)
		{
			int[][] resultMultipliedMatrix;
			//int partialSum;
			
			resultMultipliedMatrix = new int[ARowCount][BColumnCount];
			
			if(isSymmetric)
			{
				int numberOfCores;
				numberOfCores = GlobalClass.RunningValues.maximumNumberOfCPUCoresToBeUsedForNotMuchRamRequiringAndTimeConsumingTasks;
				matrixMultiplierProcessorPool = new matrixMultiplierProcessorThreadClass[numberOfCores];
				for(int i=0; i<numberOfCores; i++)
				{
					matrixMultiplierProcessorPool[i] = new matrixMultiplierProcessorThreadClass(i, matrixA, matrixB, ARowCount, SharedRowColumnCount, BColumnCount, resultMultipliedMatrix, numberOfCores, isSymmetric);
					matrixMultiplierProcessorPool[i].start();
			
				}
				
				for(int i=0; i<numberOfCores; i++)
				{				
					try
					{
						matrixMultiplierProcessorPool[i].join();
					}
					catch(Exception e)
					{
						e.printStackTrace();
					}	
				}
				
				/*for(int i = 0; i < ARowCount; i++)
				{			
					//System.out.println("i:"+i);
					for(int j = 0; j <= i; j++) 
					{
						partialSum = 0;
						
						for(int k = 0; k < SharedRowColumnCount; k++)
						{
							partialSum += matrixA[i][k] * matrixB[k][j];		 
						}
						resultMultipliedMatrix[i][j] = partialSum; 
					} 
				 }
				
				for(int i = 0; i < ARowCount; i++)
				{
					for(int j = i+1; j < SharedRowColumnCount; j++)
					{
						resultMultipliedMatrix[i][j] = resultMultipliedMatrix[j][i]; 					
					}			
				}*/
			}
			else
			{
				int numberOfCores;
				numberOfCores = GlobalClass.RunningValues.maximumNumberOfCPUCoresToBeUsedForNotMuchRamRequiringAndTimeConsumingTasks;
				matrixMultiplierProcessorPool = new matrixMultiplierProcessorThreadClass[numberOfCores];
				for(int i=0; i<numberOfCores; i++)
				{
					matrixMultiplierProcessorPool[i] = new matrixMultiplierProcessorThreadClass(i, matrixA, matrixB, ARowCount, SharedRowColumnCount, BColumnCount, resultMultipliedMatrix, numberOfCores, isSymmetric);
					matrixMultiplierProcessorPool[i].start();
			
				}
				
				for(int i=0; i<numberOfCores; i++)
				{				
					try
					{
						matrixMultiplierProcessorPool[i].join();
					}
					catch(Exception e)
					{
						e.printStackTrace();
					}	
				}
				
				/*
				for(int i = 0; i < ARowCount; i++)
				{			
					//System.out.println("i:"+i);
					for(int j = 0; j < SharedRowColumnCount; j++) 
					{
						partialSum = 0;
						
						for(int k = 0; k < SharedRowColumnCount; k++)
						{
							partialSum += matrixA[i][k] * matrixB[k][j];		 
						}
						resultMultipliedMatrix[i][j] = partialSum; 
					} 
				 }*/		
			}		
			
			return resultMultipliedMatrix;		
		}
		
		
		void createAdjacencyMatrix()
		{
			ArrayList<NodeClass> s;
			
			for(int i=0; i<oneDimensionalLength;i++)
			{
				s=localg.getDataSet().get(i).getEdgeList().get(localEdgeType).getNeigbours();
				for(int j=0; j<s.size();j++)
				{
					int order = s.get(j).getOrder();
					komsulukMatrisi[localg.getDataSet().get(i).getOrder()][order] = 1;				
				}			
			}	
			komsulukMatrisiAtLastLevel  = komsulukMatrisi;			
			updateShortestPathsArray();
		}

		
		void printMatrix(int[][] matrixToBePrinted, int rowCount, int columnCount, String comment)
		{
			System.out.println(comment);
			
			for(int i=0; i<rowCount; i++)
			{
				for(int j=0; j<columnCount; j++)
					System.out.print(matrixToBePrinted[i][j]+" ");

				System.out.println();					
			}		
			
			System.out.println();
		}

		void printLastAdjacencyMatrix()
		{		
			System.out.println("AdjacencyMatrixL("+lastValidLevel+")");
			for(int i=0; i<oneDimensionalLength; i++)
			{
				for(int j=0; j<oneDimensionalLength; j++)
					System.out.print(komsulukMatrisiAtLastLevel[i][j]+" ");

				System.out.println();					
			}		
		}
		
		void printShortestArrayMatrix()
		{	
			System.out.println("Shortest Path Array:");
			
			System.out.println("oneDimensionalLength:"+oneDimensionalLength);
			for(int i=0; i<oneDimensionalLength; i++)
			{
				for(int j=0; j<oneDimensionalLength; j++)
					System.out.print(shortestPathArray[i][j]+" ");

				System.out.println();					
			}			
			
			System.out.println();
		}
		
		boolean checkIfItIsTimeStopIterationsOfCalculations(int level, boolean isSymmetric)
		{		
			if(checkIfNewNoNewNodesBecameReachableAtLastStep(isSymmetric))
				return true;
				
			for(int i=0; i<oneDimensionalLength; i++)
				for(int j=0; j<oneDimensionalLength; j++)
					if(shortestPathArray[i][j]==-1)
					{
						if(level <= oneDimensionalLength-1)
							return false;
						else 
							return true;
					}		
			return true;
		}
		
		public int findShortestPathBetween(NodeClass a, NodeClass b)
		{
			int orderOfNodeA, orderOfNodeB;
			orderOfNodeA = a.getOrder();
			orderOfNodeB = b.getOrder();
			
			return shortestPathArray[orderOfNodeA][orderOfNodeB];		
		}

		void updateShortestPathsArray()
		{			
			int buKademedeBulunanYolSayisi=0;
			//System.out.println("Updating shortest paths for level:"+lastValidLevel);
			for(int i=0; i<oneDimensionalLength; i++)
				for(int j=0; j<oneDimensionalLength; j++)
					if(komsulukMatrisiAtLastLevel[i][j]!=0 && shortestPathArray[i][j]==-1)
					{
						buKademedeBulunanYolSayisi++;						
						shortestPathArray[i][j]=lastValidLevel;
						//System.out.println("["+(i+1)+"]["+(j+1)+"]");
					}
			
			toplamBulunanYolSayisi += buKademedeBulunanYolSayisi;
			//System.out.println("YolSayisi:" + buKademedeBulunanYolSayisi);
			//System.out.println("toplamBulunanYolSayisi:" + toplamBulunanYolSayisi);
			
			
		}
		
		public class matrixMultiplierProcessorThreadClass extends Thread
	    {
	        int index;
	        int[][] matrixA;
	        int[][] matrixB;
	        int ARowCount;
	        int AColumnCount;
	        int BRowCount;
	        int[][] multiResultMultipliedMatrix;
	        int numberOfAvailableCores;
	        boolean isSymmetric;
	        
	        
	         
	        matrixMultiplierProcessorThreadClass(int index, int[][] matrixA, int[][] matrixB, int ARowCount, int AColumnCount, int BRowCount, int[][] resultMultipliedMatrix, int numberOfAvailableCores, boolean isSymmetric)
	        {
	             this.index=index;
	             
	             this.matrixA=matrixA;
	             this.matrixB=matrixB;
	             
	             this.ARowCount=ARowCount;
	             this.AColumnCount=AColumnCount;	             
	             this.BRowCount=BRowCount;
	             
	             this.numberOfAvailableCores=numberOfAvailableCores;
	             
	             multiResultMultipliedMatrix = resultMultipliedMatrix;
	             
	             this.isSymmetric = isSymmetric;
	        }
	        
	        
	        public void run() 
	        {
        		int SharedRowColumnCount = AColumnCount; 
        		int partialSum;
        		
	        	if(isSymmetric)
	        	{
	        		int rowStartIndex=(int) Math.floor((double)(ARowCount*Math.sqrt(index)/Math.sqrt(numberOfAvailableCores)));
	        		int rowEndIndex=  (int) Math.floor((double)(ARowCount*(Math.sqrt(index+1))/Math.sqrt(numberOfAvailableCores)));	        	

	        		if(rowEndIndex>ARowCount)
	        			rowEndIndex=ARowCount;
	        		
	        		//System.out.println("Sym For index "+index+" rowStartIndex:"+rowStartIndex);
	        		//System.out.println("Sym For index "+index+" rowEndIndex:"+rowEndIndex);
	        		
	        		int yapilanHesapSayisi;
	        		int toplamHesapSayisi;
	        		
	        		toplamHesapSayisi = rowEndIndex - rowStartIndex;
	        		
					for(int i = rowStartIndex; i < rowEndIndex; i++)
					{	
						yapilanHesapSayisi = i - rowStartIndex;		
						
						//System.out.println("Kalan("+index+"):"+yapilanHesapSayisi+"/"+toplamHesapSayisi);
						//System.out.println("i:"+i);
						for(int j = 0; j <= i; j++) 
						{
							partialSum = 0;
							
							for(int k = 0; k < SharedRowColumnCount; k++)
							{
								partialSum += matrixA[i][k] * matrixB[k][j];		 
							}
							multiResultMultipliedMatrix[i][j] = partialSum; 
						} 
					 }
					
					for(int i = rowStartIndex; i < rowEndIndex; i++)
					{
						for(int j = i+1; j < SharedRowColumnCount; j++)
						{
							multiResultMultipliedMatrix[i][j] = multiResultMultipliedMatrix[j][i]; 					
						}			
					}        		
	        	}
	        	else
	        	{
	        		int rowStartIndex=(int) Math.floor((double)(ARowCount*index)/numberOfAvailableCores);
	        		int rowEndIndex=  (int) Math.floor((double)(ARowCount*(index+1)/numberOfAvailableCores));

	        		if(rowEndIndex>ARowCount)
	        			rowEndIndex=ARowCount;	        		

	        		System.out.println("For index "+index+" rowStartIndex:"+rowStartIndex);
	        		System.out.println("For index "+index+" rowEndIndex:"+rowEndIndex);



	        		for(int i = rowStartIndex; i < rowEndIndex; i++)
	        		{			
	        			//System.out.println("i:"+i);
	        			for(int j = 0; j < SharedRowColumnCount; j++) 
	        			{
	        				partialSum = 0;

	        				for(int k = 0; k < SharedRowColumnCount; k++)
	        				{
	        					partialSum += matrixA[i][k] * matrixB[k][j];		 
	        				}
	        				multiResultMultipliedMatrix[i][j] = partialSum; 
	        			} 
	        		}
	        	}
	        }
	    }
		
		void makeShortestPathCalculationsOverConnectedComponents()
		{
			double numberOfPathsFound=0;
			double cumulativeLengthOfThePaths=0;
			int shortestPathOfTheElements;
			double diameter=0;
		
			for(int i = 0; i < oneDimensionalLength; i++)
				for(int j = 0; j < i; j++)
				{
					shortestPathOfTheElements=shortestPathArray[i][j];
					if(shortestPathOfTheElements > 0)
					{
						numberOfPathsFound++;
						cumulativeLengthOfThePaths+=shortestPathOfTheElements;
						if(shortestPathOfTheElements > diameter)
							diameter = shortestPathOfTheElements;
							
					}					
				}
			System.out.println("FROM MATRIX: numberOfPathsFound:"+ numberOfPathsFound+" cumulativeLengthOfThePaths:"+cumulativeLengthOfThePaths+" Avg.Path Length:"+cumulativeLengthOfThePaths/numberOfPathsFound+" diameter:"+diameter);
			
		}
		
		boolean checkIfNewNoNewNodesBecameReachableAtLastStep(boolean isSymmetric)
		{	
			if(isSymmetric)
			{				
				for(int i = 0; i < oneDimensionalLength; i++)
					for(int j = i; j < oneDimensionalLength; j++)
					{
						if((i!=j) && ((komsulukMatrisiAtLastLevel[i][j]!=0 && shortestPathArray[i][j]==-1)))
							return true;
					}
				return false;
			}
			else
			{
				for(int i = 0; i < oneDimensionalLength; i++)
					for(int j = 0; j < oneDimensionalLength; j++)
					{
						if((i!=j) && (komsulukMatrisiAtLastLevel[i][j]!=0 && shortestPathArray[i][j]==-1))
							return false;
					}
				return true;			
			}
		}
	            
	    private int A_row;
	    private int A_col;
	    private int B_row;
	    private int B_col; 	    private int[][] matrix_A;
	    private int[][] matrix_B;
	    private int[][] mult_ans;
	    private matrixMultiplierProcessorThreadClass[] matrixMultiplierProcessorPool;
}
